package com.study.suanfa.paixu;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;

/**
 * @description: charu   插入排序
 * @date: 2020/11/25 12:26
 * @author: hcm
 * @version: 1.0
 */
public class charu {

    public static void main(String[] args) {

        int[] arr = randomArray(0,80000,80000);
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String d1 = simpleDateFormat.format(date1);
        System.out.println("排序前："+d1);
        instertSort(arr);
        Date date2 = new Date();
        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String d2 = simpleDateFormat2.format(date2);
        System.out.println("排序后："+d2);
    }

    /**
     * 插入排序 步骤
     * 1）创建一个插入排序的方法，里面传入一个数组
     * 2）插入排序是找到最小的元素然后插入到前面，所以需要遍历，并且有个需要比较的下标
     * 3）遍历中，如果当前下标元素大于比较下标元素，比较下一个，跳过这次循环
     * 4）如果找到小于当前值的比较下标，开启内循环置换位置
     *
     * @param arr
     */
    private static void instertSort(int[] arr) {
        //长度
        int length = arr.length;

        //比较值下标
        int compareIndex = 0;

        //遍历
        for (int i = 1; i < length; i++) {

            if (arr[i] > arr[compareIndex]) {
                compareIndex += 1;
                continue;
            }

            int len = compareIndex;
            int currentIndex = i;
            //内循环遍历寻找插入下标
            while (arr[currentIndex] < arr[len]) {

                int temp = arr[len];
                //交换
                arr[len] = arr[currentIndex];
                arr[currentIndex] = temp;
                //继续找
                if(len > 0){
                    len--;
                }

                currentIndex--;
            }

            compareIndex++;
        }
        System.out.println(Arrays.toString(arr));
    }

    public static int[] randomArray(int min,int max,int n){
        int len = max-min+1;

        if(max < min || n > len){
            return null;
        }

        //初始化给定范围的待选数组
        int[] source = new int[len];
        for (int i = min; i < min+len; i++){
            source[i-min] = i;
        }

        int[] result = new int[n];
        Random rd = new Random();
        int index = 0;
        for (int i = 0; i < result.length; i++) {
            //待选数组0到(len-2)随机一个下标
            index = Math.abs(rd.nextInt() % len--);
            //将随机到的数放入结果集
            result[i] = source[index];
            //将待选数组中被随机到的数，用待选数组(len-1)下标对应的数替换
            source[index] = source[len];
        }
        return result;
    }
}
